#include <iostream>
#include <iomanip>
#include <fstream>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <numeric>
#include <vector>
#include <iterator>
#include <functional>
#include <boost/bind.hpp>
#include <boost/timer.hpp>
#include <boost/shared_ptr.hpp>

using namespace std;

template<typename T>
class Heap
{
public:
	Heap():vec(NULL),heap_size(0){}
	Heap(vector<T> *V):vec(V),heap_size(V->size()){}

	void fix_down(int pos)
	{
		int l = left(pos);
		int r = right(pos);
		int min = pos;
		if( l>0 && vec->at(l) < vec->at(pos) )
			min = l;
		if( r>0 && vec->at(r) < vec->at(min) )
			min = r;
		if(min != pos)
		{
			swap<T>( vec->at(min), vec->at(pos) );
			fix_down(min);
		}
	}

	void build_heap()
	{
		int i=heap_size/2;
		while(i>=0)
			fix_down(i--);
	}

	void heapsort()
	{
		while(--heap_size)
		{
			swap<T>( vec->at(0), vec->at(heap_size) );
			fix_down(0);
		}

		heap_size = vec->size();
	}

private:

	int left(int pos)
	{
		int l = 2*pos + 1;
		return l<heap_size?l:-1;
	}

	int right(int pos)
	{
		int r = 2*pos + 2;
		return r<heap_size?r:-1;
	}

	vector<T>   *vec;
	size_t       heap_size;
};

struct Rand
{
	int range;
	Rand(int r=100):range(r){}
	int operator()()
	{
		return rand()%range;
	}
};

int main(int argc, char** argv)
{
	srand(static_cast<int>(time(0)));
	const int size = 30;
	vector<int> V(size);
	generate(V.begin(),V.end(),Rand(size));
	Heap<int> H(&V);
	H.build_heap();
	H.heapsort();
	copy(V.begin(),V.end(),ostream_iterator<int>(cout,"  "));
	cout<<endl;

	return 0;
}
